# 354. 俄罗斯套娃信封问题
# https://leetcode-cn.com/problems/russian-doll-envelopes/
#
# 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
# 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
# 请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
#
# 注意：不允许旋转信封。
#
# 示例 1：
#
# 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
# 输出：3
# 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
# 示例 2：
#
# 输入：envelopes = [[1,1],[1,1],[1,1]]
# 输出：1
#
# 提示：
#
# 1 <= envelopes.length <= 5000
# envelopes[i].length == 2
# 1 <= wi, hi <= 104
#
# 讨论:
# maxEnvelopes1方法中, 之前每次更新d[i]时我使用的是max(sorted_E, lambda x: ...)超时了, 后来我通过for循环迭代求反而AC了
from typing import List


class Solution:
    @staticmethod
    def print_trip(_pkg: dict, _sorted_E, _i: int):
        ss = [_sorted_E[_i][1]]
        if _i in _pkg:
            ss += Solution.print_trip(_pkg, _sorted_E, _pkg[_i])
        return ss

    def maxEnvelopes1(self, envelopes: List[List[int]]) -> int:
        """
        :param envelopes:
        :return:
        """
        # 最终结果
        d = list(1 for _ in range(0, len(envelopes)))

        # S1, 按(w, h)排序
        sorted_E = list(sorted(envelopes, key=lambda x: (x[0], x[1])))

        # S2, 求h的逆排序, 及每个位次对应的
        i = -1
        for w, h in sorted_E:
            i += 1
            if i == 0:
                continue
            for j in range(0, i):
                if sorted_E[j][1] < h and sorted_E[j][0] < w:
                    d[i] = max(d[j] + 1, d[i])
        return max(d)

    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        """
        优化版本
        ----
        先按照宽度排序, 同样宽度的取长度较
        2 {3}
        5 {4}
        6 {4, 7}
        7 {5, 6, 8}

        转为求最长递增子序列问题:
        max_length = 0  # 最长子序列长度
        tails = [0 for _ in range(len(sorted_by_widths))]  # 长度为
        for width, heights in sorted_by_widths:
            # heights从小到大排列
            for h in heights:
                k  # 求k=min{k | tails[k] > h, k <= max_length}
                if k 存在:
                    tails[k] = h
                else:
                    max_length += 1
                    tails[max_length] = h
                    break;
        :param envelopes:
        :return:
        """
        # S1, 按宽度由小到大排序, 同样宽度的话, 高度由大到小(这样求最长递增子序列时, 同样宽度的信仅凭高度就不会发生套娃了, 此处非常精妙)
        sorted_by_widths = sorted(envelopes, key=lambda x: (x[0], -x[1]))

        # S2, 求最长子序列
        # 最长子序列
        max_length = 0  # 最长子序列长度
        tails = [0 for _ in range(len(sorted_by_widths) + 1)]  # 长度为i的序列尾部元素, 头部中长度为0的尾部元素用不到, 默认为0

        for idx in range(len(sorted_by_widths)):
            h = sorted_by_widths[idx][1]
            # 二分查找: k=min{k | tails[k] > h, k <= max_length}
            i, j = 0, max_length + 1
            while i < j:
                m = (i + j) // 2
                if tails[m] < h:
                    i += 1
                else:
                    j = m
            tails[i] = h
            if i == max_length + 1:
                max_length += 1
        return max_length


print('num:', Solution().maxEnvelopes1([[5, 4], [6, 4], [6, 7], [2, 3]]))
print('num:', Solution().maxEnvelopes1([[1, 1], [1, 1], [1, 1]]))
print('num:', Solution().maxEnvelopes([[5, 4], [6, 4], [6, 7], [2, 3]]))
print('num:', Solution().maxEnvelopes([[1, 1], [1, 1], [1, 1]]))
print('num:', Solution().maxEnvelopes(
    [[2, 100], [3, 200], [4, 300], [5, 500], [5, 400], [5, 250], [6, 370], [6, 360], [7, 380]]))
